import java.util.List;

public class Leetcode449 {
    public static void main(String[] args) {
        List<Integer> list = List.of(1, 2, 3, 4);
        subsets(list);
    }

    //枚举集合子集
    /*
     * 要求打印出所有的子集
     * 1
     * 2
     * 3
     * 4
     * 12
     * 13
     * 14
     * 23
     * 24
     * 34
     * 123
     * 124
     * 134
     * 234
     * 1234
     * */
    public static void subsets(List<Integer> list) {
        for (int i = 1; i < 1 << list.size(); i++) {
            for (int j = 0; j < list.size(); j++) {
                if ((i & (1 << j)) != 0) {
                    System.out.print(list.get(j));
                }
            }

            System.out.println();
        }
    }


    public static int add(int a, int b) {
        if (b == 0) {
            return a;
        }

        if (a == 0) {
            return b;
        }

        return add(a ^ b, (a & b) << 1);
    }


    public static class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder builder = new StringBuilder();
            serialize(root, builder);
            return builder.toString();

        }

        private void serialize(TreeNode root, StringBuilder builder) {
            if (root == null) {
                return;
            }

            builder.append(root.val);
            serialize(root.left, builder);
            serialize(root.right, builder);
        }


        public TreeNode deserialize(String data) {
            return deserialize(data, 0, data.length() - 1);
        }

        private TreeNode deserialize(String data, int l, int r) {
            if (l > r) {
                return null;
            }

            int val = data.charAt(l), mid = l;
            TreeNode root = new TreeNode(val);
            while (mid < r && data.charAt(mid + 1) < val) {
                mid++;
            }

            root.left = deserialize(data, l + 1, mid);
            root.right = deserialize(data, mid + 1, r);
            return root;
        }
    }
}

